#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <set>

using namespace std;

class Matrix
{
    public :
        inline unsigned int getSize() const
        {
            return _vvMatrix.size();
        }

        inline double get(const unsigned int &x, const unsigned int &y) const
        {
            return _vvMatrix[x][y];
        }

        void set(unsigned int x, unsigned int y, double d)
        {
            _vvMatrix[x][y] = d;
            _vvMatrix[y][x] = d;
        }

    //private :
        std::vector<std::vector<double> > _vvMatrix;
};


std::ostream& operator << (std::ostream& os, const Matrix& m) 
{
    os << m.getSize() << endl;
    for (unsigned int i = 0; i < m.getSize(); i++)
    {
        for (unsigned int j = 0; j < m.getSize(); j++)
            os << m.get(i,j) << "\t";
        os << endl;
    }
    return os; 
}



std::istream& operator >> (std::istream& is, Matrix& m)
{
    unsigned int size;
    is >> size;

    m._vvMatrix.resize(size);
    for (unsigned int i = 0; i < m._vvMatrix.size(); i++)
        m._vvMatrix[i].resize(size);

    for (unsigned int i = 0; i < m._vvMatrix.size(); i++)
        for (unsigned int j = 0; j < size; j++)
        {
            double d;
            is >> d;
            m.set(i, j, d);
        }

    return is;
}


double calculateDelta( const Matrix &m )
{
    Matrix result = m;
    double delta;

    double vXY;
    unsigned int x;

    for (unsigned int fx = m.getSize()-1; fx > 1; fx--)
    {
        for (unsigned int y = 0; y < (m.getSize()-fx); y++)
        {
            x = fx+y;
            vXY = result.get( x, y );
            if( result.get( x-1, y) > vXY )
                result.set( x-1, y, vXY);
            if( result.get( x,   y+1) > vXY )
                result.set( x,   y+1, vXY);
        }
    }

    double maxDiff=0;
    for (unsigned int x = 0; x < m.getSize(); x++)
        for (unsigned int y = x+1; y < m.getSize(); y++)
        {
            if( maxDiff < (m.get( x, y ) - result.get(x, y) ))
                maxDiff = m.get( x, y ) - result.get(x, y);
        }

    delta = (maxDiff/2.0);

    return delta;
}



double searchBestMatrix(const Matrix &m, std::set<unsigned int> &list, std::vector<unsigned int> &order)
{
    double tmp;
    double best;
    best = -1;

    if( list.size() == 0 )
    {
        double delta;


        Matrix mTmp = m;

        for (unsigned int i = 0; i < order.size(); i++)
        {
            for (unsigned int j = 0; j < order.size(); j++)
            {
                if(i==j)
                    continue;

                mTmp.set( i, j, m.get( order[i], order[j] ) );
            }
        }

        return calculateDelta(mTmp);
    }

    for (std::set<unsigned int>::iterator it = list.begin(); it != list.end(); ++it)
    {
        std::set<unsigned int> list2(list);
        order.push_back( *it );
        list2.erase( *it );
        tmp = searchBestMatrix( m, list2, order );
        order.pop_back();

        if((best==-1) || (tmp < best))
            best = tmp;
    }

    return best;
}

double optimalRobinsonMatrix(const Matrix &m)
{
    std::set<unsigned int> list;
    std::vector<unsigned int> order;

    for (unsigned int i = 0; i < m.getSize(); i++)
        list.insert(i);
    
    return searchBestMatrix(m, list, order);
}



void showHelp(std::string a)
{
    std::cerr << "usage: \t";
    std::cerr << "\t" << a;
    std::cerr << " [-i input-file]";
    std::cerr << std::endl;
}


void showErrorSyntax(std::string a)
{
    std::cerr << "Syntax error" << std::endl;
    showHelp(a);
    exit(-1);
}

int main(int argc, char const* argv[])
{
    Matrix m;
    bool searchOpt=false;


    int pos=1;

    while(pos < argc)
    {
        if( (strlen(argv[pos]) != 2) || (argv[pos][0] != '-') )
            showErrorSyntax(argv[0]);

        switch( argv[pos][1] )
        {
            case 'I' :
            case 'i' :
                {
                    if( m.getSize() > 0)
                        showErrorSyntax(argv[0]);

                    ifstream file( argv[pos+1] );
                    if( !file )
                    {
                        cerr << "can't open file : " << argv[1] << endl;
                        return -10;
                    }

                    file >> m;

                    pos+=2;

                    break;
                }

            case 'o' :
            case 'O' :
                searchOpt = true;
                ++pos;
                break;

            case 'h' :
            case 'H' :
                showHelp(argv[0]);
                return 0;

            default :
                showErrorSyntax(argv[0]);
        }
    }

    if( m.getSize() == 0 )
        cin >> m;


    double outDelta;
    if(searchOpt)
        outDelta = optimalRobinsonMatrix(m);
    else
        outDelta = calculateDelta(m);

    std::cout << outDelta << std::endl;

    return 0;
}
